/*
 * Question: Suppose that there are two additional fields
 * 'parent' and 'mark'. The former points to the node's
 * parent, the latter (0..2) indicates whether turn to left
 * child or turn to right child. Try to travel a binary
 * in postfix order without stack.
 */

#include <iostream>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
public:
    int mark;
    bitree *parent;
};

void preprocess(bitree *rt)
{
    if(!rt) return;
    rt->mark = 0;
    if (rt->lchild) rt->lchild->parent = rt;
    if (rt->rchild) rt->rchild->parent = rt;
    preprocess(rt->lchild);
    preprocess(rt->rchild);
}

void visit(bitree *rt)
{
    cout << rt->key << " ";
}

void postorder(bitree *rt)
{
    bitree *p;

    p = rt;
    while(p) {
        if(p->mark == 0) {
            /* preorder: visit(p); */
            p->mark = 1;
            if(p->lchild) p = p->lchild;
        } else if(p->mark == 1) {
            /* inorder: visit(p); */
            p->mark = 2;
            if(p->rchild) p = p->rchild;
        } else {
            visit(p);
            p->mark = 0;
            p = p->parent;
        }
    }
}

int main()
{
    bitree *rt;

    bitree_create<bitree,char>(rt, "ex39.txt");
    preprocess(rt);
    postorder(rt);
    cout << endl;
    bitree_destory(rt);

    return 0;
}
